1929年,当约翰*文森特*阿塔纳索夫在威斯康星大学攻读物理博士学位时,十七岁的阿兰*图灵(生于1912年6月23日)正在参加毕业考试。数学阅卷人在他的答题纸上写了这么一段话:“他做代数验证时缺乏耐心,还经常因为字写得太差而丢分--有时是因为他的字太难辨认,有时是因为他看错了自己之前写的字然后导致后面的错误。”他总共参加了三次考试,为了拿到梦寐以求的剑桥大学国王学院的录取通知书(有奖学金),他把专业从科学改为数学。
阿兰*图灵在谢伯恩学校的生活以悲剧告终--在学校最后一年(1930年)的冬天,他的好朋友克里斯托弗*莫科姆死于肺结核。莫科姆比图灵大一点,具有图灵所没有的明星气质,在谢伯恩赢得了不少荣誉,后来获得了三一学院的奖学金。这两位年轻人有着共同的科学爱好和数学爱好,图灵不仅尊重莫科姆的聪明才智,还有他的全面发展以及他文学的兴趣爱好--他会弹钢琴,作业也写得非常认真,从不出现低级错误。更重要的是,他非常有趣--跟其他恶作剧爱好者一样,他曾经让一个装满瓦斯的气球飞过谢伯恩女生的头顶。也许,正是因为莫科姆的积极影响,图灵才有可能在谢伯恩学校最后时间里频繁获得高分。
1931年,图灵获得了剑桥大学国王学院的奖学金,并不是三一学院的。如果说在佛罗里达州大学和艾奥瓦州立学院,甚至是威斯康星大学,阿塔纳索夫总是游走在数学和物理学的外围,那么在国王学院,图灵和他也有着同样的困惑,尤其是在数学方面。他师从天体物理学家亚瑟*爱丁顿和两位数学家--高德菲*哈罗德*哈代和麦克斯*玻恩。他在那里遇到了约翰*冯*诺依曼--他是众多逃离纳粹德国并在别处定居的数学家之一。在地志学教授麦克斯*纽曼的引导下,图灵接触到足以让他功成名就的希尔伯特问题。其实解决希尔伯特问题并不是图灵的第一要务,有个教授曾经建议他研究水的介电常数,但是他被搞得晕头转向也没什么成果。
德国数学家大卫*希尔伯特在1928年提出“可判定性问题”(其名的二十三个希尔伯特问题之一),用门外汉的话说,“可判定性问题”指是否有这样一个程序(或者算法)可以或能够证明一个数学陈述是正确还是错误的。对当时的数学家来说,“可判定性问题”看起来很像是一个心理学、认识学或神学问题。阿兰*图灵对这个问题的答案是“没有”--并没有这样一个算法来证明所有的数学陈述是否正确。在美国普林斯顿任职的数学家阿隆佐*邱奇比图灵早几周发现这个答案。邱奇用微积分这样一种逻辑系统给这个问题提供了答案。图灵的答案充分发挥了他的想像力,他解决问题的方式和阿塔纳索夫有点类似--他在康河河岸跑步的时候找到了灵感。他是一个热爱跑步的人,有时候一直往北跑到离剑桥二十英里的伊莱。一天,他跑累了在草地上休息的时候,突然想到一个简单的程序,或者说是一串指令,能让机器运转起来。
他在论文中写到了这个方法,图灵描述了做一个简单但是很艰难的心理过程。他想像做计算的这个人被给予了一系列的指令,如果她每次都能按照指令来完成工作,她的大脑会一直以同一种方式思考,这样就不会犯计算错误(尽管这项工作会无比的枯燥无味)。很快。图灵就从一系列的指令联想到了一个完美的机器设想--能够自己运行,不需要人工干预。它可以一直运行一些程序,这些只有有限数字的程序很容易被设定。他描述了一个装入了很长胶带的机器。胶带被分为几个正方形,每一个都有一个标记或是空白。当机器扫描任何一个有标记或没有标记的的方形时,它会被要求运行一个程序--在空白的方形里填入标记,在有标记的方形里删除标记,然后右移一格或左移一格。每一个程序在运行完毕后,机器即可往前运行下一条指令,它扫描新的方形然后对这个方形按照指令进行操作--指令应该和计算一起向前推进。这种演变被图灵称为“行为表”,我们称为程序。最终,机器到达了计算的终点--例如,它可以根据行为表的指令在删除一个标记并往左移之后停下来。这样的操作显示已经求解出了答案--如果有附加的问题,被标记的方形相加就是问题所列出的标记的总和。
图灵设想了解决那些能够解决和不能够解决的数学问题能够用到的所有机器。求解这些问题所需要的东西其实只是一系列的指令和时间(和一个包含符号和空格的二进制系统),如果可以解决一个问题,那么机器就可以一直运行到问题结束。如果不能解决,那么机器就会卡住--一个错误的指令序列会让机器只能前进或后退,不停的消除并复制两个同样的方块。随后,图灵又想出了一个全面的机器,他称为“通用机器”,通过给机器足够的指令,能够解决所有特制机器能够解决的任何问题。他提出只要有足够的时间和指令,这样的机器是可以制造出来的。他解决“可判定性问题”的杀手锏是:设想他的机器如何能解决任何一个问题,他能很轻易地看到如何给机器一个能够让机器停止运转的指令的问题--也就是说,让它不停地重复一项操作而不达成任何解决方案。唯一一个能确定问题能否解决的办法就是想尽一切办法解决它们。数学无法提前设计出一种方案预测任何一个问题是否能够被解决,因此,不一定能确定一个给定陈述的真实性。此外,尽管机器能不停地运转,但人们找不到一种让机器自查的办法。因此也无法确定机器给出的答案正确与否。
微积分“展现了抽象和变化的数学过程具有优雅和强大的象征意义”,但是图灵机是一种思想实验,设想的是一种机械装置,可以通过机械或者人的大脑来完成。图灵的传记作家安德鲁*哈吉斯指出,图灵的想法“不仅仅是抽象数学的问题,也不仅是一堆符号的游戏,因为它牵涉到人类在物理世界的所作所为的思考……他的机器--不久后被称为图灵机--是一座桥梁,连接抽象的符号和物理世界。他的创意对剑桥来说真是令人震惊的”。
1936年5月,阿兰*图灵向《伦敦数学协会会报》提交了一篇名为《论可计算数,可判定性应用》的论文,但是没能如愿申请到普贤林斯顿大学的普贤科特奖学金。对当时所有的英格兰人而言,只有图灵和美国的阿隆佐*邱奇才能解释可判定性。英格兰当时没人有资格给图灵或者邱奇的论文做评审。
阿塔纳索夫和图灵用各自不同的方式证明了计数是计算的未来,但是二人之间的差异也十分明显--阿塔纳索夫需要发明一个实实在在的机器,开关一开就能运行有用的功能。图灵设想的是一种重复机械过程,但是由于他自己并不是一个喜欢搞小发明的人,他也没有从他那些有发明天赋的祖先那里继承到工程设计方面的天赋,他的机器最主要的作用是激发别人的发明灵感,而不是成为发明本身。但是计算机的第三个最早期的发明家康拉德*楚泽想的与阿塔纳索夫和图灵一点儿也不一样。